package com.asia.algorithmcode.binaryTree;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * @DESCRIPTION: 100、相同的树 ，写出了两种方法的实现，时间上都是100
 * @USER: wanfu
 * @DATE: 2025/5/9 星期五 10:55
 */
public class IsSameTree {


    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);


//        n3.left = n1;
        n3.right = n4;
        n4.left = n2;
//        n1.left = n3;
//        n3.right = n2;


        n1.left = n2;
        n1.right = n3;


        System.out.println(new IsSameTree().isSameTree(n1, n3));

        System.out.println(" ");
    }


    /**
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if ((p == null && q != null) ||
                (p != null && q == null) ||
                (p != null && p.val != q.val)) {
            return false;
        }
        if (p != null && q != null && !isSameTree(p.left, q.left)){
            return false;
        }
        if (p != null && q != null &&!isSameTree(p.right, q.right)) {
            return false;
        }
        return true;
    }


    /**
     * 方法一、使用相同的方法进行遍历，遍历的结果相同则两个树是相同的， 否则则是不同的
     * @param p
     * @param q
     * @return
     */
//    public boolean isSameTree(TreeNode p, TreeNode q) {
//        dfs1(p);
//        dfs2(q);
//        if (list1.size() != list2.size()) {
//            return false;
//        }
//        for (int i = 0; i <  list1.size(); i++) {
//            if (!Objects.equals(list1.get(i), list2.get(i))) {
//                return false;
//            }
//        }
//        return true;
//    }
//    List<Integer> list1 = new ArrayList<>();
//    List<Integer> list2 = new ArrayList<>();
//
//    public void dfs1(TreeNode root){
//        if (root == null){
//            list1.add(Integer.MIN_VALUE);
//            return;
//        }
//        list1.add(root.val);
//        dfs1(root.left);
//        dfs1(root.right);
//    }
//
//    public void dfs2(TreeNode root){
//        if (root == null){
//            list2.add(Integer.MIN_VALUE);
//            return;
//        }
//        list2.add(root.val);
//        dfs2(root.left);
//        dfs2(root.right);
//    }

}


